#/usr/bin/python
#coding: utf-8 -*-

'''
Alogrithme du tabou pour la résolution du problème d'approvisionnement des villes de WOW par les entrepots.
'''

import logging, random, math, copy
import GloutonSolver
from topology import topology

class ListTaboo(object):
	def __init__(self):
		self.listTaboo	= []
		self.size	= 10
				
	def addTaboo(self, t):
		if len(self.listTaboo) == self.size:
			# Pop the first element
			self.listTaboo.pop(0)
		# Insert the arg given in argument
		self.listTaboo.append(t)	
	
	def getTaboo(self):
		pass
	


class TabooSolver(object):
	def __init__(self, Topo = None):
		self.topology		= Topo
		self.listTaboo		= None
		self.SGlouton		= GloutonSolver.GloutonSolver(Topo) 
		self.taboo()
		

        ''' Recherche de voisin '''
        def generateNeighbour(self, S):            
            # On prend alÃ©atoirement une opÃ©ration du traceur de S
            operation = S.tracer[random.randint(0, len(S.tracer)-1)]
            logging.debug('')
            logging.debug(operation.display())
            
            # if Tracer.CREATION : on commence par un autre entrepot (au hasard), puis on dÃ©roule l'algo du glouton
            if operation.typeOperation == Tracer.CREATION:
                whIndex = S.warehouses.index(self.getWarehouse(S, operation.origine))

                # On prend l'entrepot juste avant ou juste apres                
                if whIndex <= 0:
                    # 1er element, on en prend un parmi tous ceux qui sont aprÃ¨s
                    newWh = S.warehouses[random.randint(1, len(S.warehouses)-1)]
#                    print('1er element, on prend ' + newWh.name)
                elif whIndex == len(S.warehouses)-1:
                    # dernier element, on en prend un parmi tous ceux qui sont avant
                    newWh = S.warehouses[random.randint(0, len(S.warehouses)-2)]
#                    print('dernier element, on prend ' + newWh.name)                
                else:
                    # On en prend un au hasard (exceptÃ© l'entrepot courant)
                    whpop = S.warehouses.pop(whIndex)
                    newWh = S.warehouses[random.randint(0, len(S.warehouses)-1)]
                    S.warehouses.append(whpop)
#                    print('AU PIF, on prend ' + newWh.name)                          


                # On effectue les K-1 opÃ©ration pour gÃ©nÃ©rer le dÃ©but de la nouvelle solution
                newS = self.createNewSolution(S, operation, self.getOperation(S, Tracer.CREATION, newWh.name))

                # On calcule la nouvelle solution (algo du glouton) avec les entrepots restants
                cost = self.findSolution(newS)

                return newS
            elif Tracer.TRANSPORT :
                logging.debug('Transport')
                newS = self.initNewTopology(S)
                while 1:
                    cpyTracer = copy.deepcopy(S.tracer)
                    # On a un transport du type E -- alpha --> V
                    # On enleve 1 ressources correspondant a delta
                    transportInitial = operation.cost/self.getRoad(S, operation.origine, operation.destination).cost
                    delta = 1
                    logging.debug('Transport initial = ' + str(transportInitial) \
                            + ' | Delta a transporter = ' + str(delta))
                    # Cherche autre opÃ©ration ou destination = Y
                    repartition = delta
                    for op in cpyTracer:
                        # PossibilitÃ© d'ajouter plus de ressource sur ce transport (assez de capa avec l'entrepot)
                        if op.destination == operation.destination:
                            logging.debug('Un transport trouve vers ' + op.destination + ' avec un autre entrepot : ' + op.origine)
                            logging.debug('Capacite de l\'entrepot : ' + op.origine + ' : ' + str(self.getWarehouse(S, op.origine).capacity))
                            if self.getWarehouse(S, op.origine).capacity >= delta:
                                # Full
                                logging.debug('L\'entrepot ' + op.origine + ' peut completement satisfaire la ville ' + op.destination)
                                op.cost += (delta * self.getRoad(S, op.origine, op.destination).cost)
                                repartition -= delta
                            elif self.getWarehouse(S, op.origine).capacity > 0:
                                # All possible
                                transferred = self.getWarehouse(S, op.origine).capacity
                                op.cost += (self.getWarehouse(S, op.origine).capacity * self.getRoad(S, op.origine, op.destination).cost)
                                repartition -= transferred
                                logging.debug('L\'entrepot ' + op.origine + ' peut seulement satisfaire la ville ' + op.destination + ' de ' \
                                      + str(transferred))
                            else:
                                logging.debug('L\'entrepot ' + op.origine + ' est vide..')

                    # VÃ©rifie si la ville V est satisfaite (delta bien rÃ©partit)
                    if repartition == 0:
                        logging.debug('Ville satisfaite')
                        # On modifie la 1ere operation
                        for c in cpyTracer:
                            if c.origine == operation.origine and c.destination == operation.destination and c.cost == operation.cost:
                                c.cost = (transportInitial - delta) * self.getRoad(S, operation.origine, operation.destination).cost
                                break
                        for ope in cpyTracer:
                            self.executeOperation(newS, ope)
                        break
                    else:
                        logging.debug('Ville non satisfaite... on cherche des entrepots ayant des capa suffisantes')
                        # On cherche des entrepots ayant des capa suffisantes pour satisfaire la ville Y
                        listNewTrace = []
                        repartition = delta
                        for op in cpyTracer:
                            if op.typeOperation == Tracer.CREATION and self.getWarehouse(S, op.origine).capacity > 0 and repartition > 0:
                                if self.getWarehouse(S, op.origine).capacity >= repartition:
                                    transferred = repartition
                                else:
                                    transferred = self.getWarehouse(S, op.origine).capacity
                                cost = (transferred * self.getRoad(S, op.origine, operation.destination).cost)
                                repartition -= transferred
                                logging.debug('L\'entrepot ' + op.origine + ' peut seulement satisfaire la ville ' + operation.destination + ' de ' \
                                      + str(transferred))
                                listNewTrace.append(Tracer(Tracer.TRANSPORT, op.origine, operation.destination, cost))
                        
                        # VÃ©rifie si la ville V est satisfaite cette fois ci (delta bien rÃ©partit)
                        if repartition == 0:
                            logging.debug('Ville ENFIN satisfaite')
                            for t in listNewTrace:
                                cpyTracer.append(t)

                            # On modifie la 1ere operation
                            for c in cpyTracer:
                                if c.origine == operation.origine and c.destination == operation.destination and c.cost == operation.cost:
                                    c.cost = (transportInitial - delta) * self.getRoad(S, operation.origine, operation.destination).cost
                                    break
                            for ope in cpyTracer:
                                self.executeOperation(newS, ope)
                            break
                        logging.debug('Ville toujours pas satisfaite. Solution pas possible. ON RECOMMENCE :-(')
                return newS
                                
                            


	''' MAJ des besoins de chacune des villes.'''
	def updateCityNeeds(self, topo, warehouse):
		# Selection des routes en provenance de l'entrepot
		warehouse_roads = []
		for road in topo.roads:
		    if road.warehouse == warehouse.name:
			warehouse_roads.append(road)
				
		# On tri les routes suivant le cout de transport (du - au + Ã©levÃ©)
		warehouse_roads.sort(lambda r1,r2:cmp(r1.cost, r2.cost))


		# MAJ des besoins des villes si nÃ©cessaire
		for road in warehouse_roads:
		    city = self.getCity(topo, road.city)
		    if city.current_needs > 0:
			# On satisfait au maximum la demande de la ville
			transferred = topo.transit(road.warehouse, road.city, city.current_needs)
			# MAJ du cout total
			topo.tracer.append(Tracer(Tracer.TRANSPORT, road.warehouse, road.city, (road.cost * transferred)))

			# break si entrepot vide
			if warehouse.is_empty():
                            break

        ''' Calcule la nouvelle solution (algo du glouton) avec les entrepots restants '''
        def findSolution(self, S):
            whNotConstructed = [item for item in S.warehouses if not item in S.constructedWarehouses]

            # MAJ a partir du dernier entrepot construit
            self.updateCityNeeds(S, S.constructedWarehouses[len(S.constructedWarehouses)-1])
            
	    # On tri les routes suivant le cout de transport (du - au + Ã©levÃ©)
	    whNotConstructed.sort(lambda r1,r2:cmp(r1.cost, r2.cost))
	    
            for wh in whNotConstructed:
                # Check s'il reste encore des villes dans le besoin
                if self.isCitiesInNeed(S):
                    # CrÃ©ation de l'entrepot
                    S.tracer.append(Tracer(Tracer.CREATION, wh.name, cost=wh.cost))
                    S.createWarehouse(wh.name)
                    
                    # MAJ des besoins de chaque ville
                    self.updateCityNeeds(S, wh)
                else:
                    # Les besoins de toutes les villes sont satisfait. Fin de l'algo
                    break


            return self.f(S)

        ''' Execute l'opÃ©ration donnÃ©e en argument sur la topologie "S"'''
        def executeOperation(self, S, ope):
            if ope.typeOperation == Tracer.CREATION:
		S.tracer.append(Tracer(Tracer.CREATION, ope.origine, cost=ope.cost))
		S.createWarehouse(ope.origine)
	    else:
                transferred = S.transit(ope.origine, ope.destination, ope.cost/self.getRoad(S, ope.origine, ope.destination).cost)
                S.tracer.append(Tracer(Tracer.TRANSPORT, ope.origine, ope.destination, ope.cost))

        ''' Initialisation d'une nouvelle topologie en se basant sur les donnÃ©es de celle donÃ©e en argument'''
        def initNewTopology(self, oldS):
            # Init new topology
            newS = topology()
            newS.warehouses = copy.deepcopy(oldS.warehouses)
            for w in newS.warehouses:
                w.capacity = w.original_capacity
            newS.cities = copy.deepcopy(oldS.cities)
            for c in newS.cities:
                c.current_needs = c.original_needs
            newS.roads = copy.deepcopy(oldS.roads)
            return newS
        
        def createNewSolution(self, oldS, operation1, operation2):
            newS = self.initNewTopology(oldS)

            # Repeat the K-1 operation
            for ope in oldS.tracer:
                # On effectue l'opÃ©ration de remplacement
                if ope == operation1:
                    self.executeOperation(newS, operation2)                    
                    break
                elif ope == operation2:
                    self.executeOperation(newS, operation1)                    
                    break
                else:
                    self.executeOperation(newS, ope)
            return newS
                    
        ''' Retourne l'opÃ©ration recherchée'''
        def getOperation(self, topo, typeOp, ori = None, dst = None, cost = 0):
            if typeOp == Tracer.CREATION:
                for op in topo.tracer:
                    if ori == op.origine:
                        return op
            elif typeOp == Tracer.TRANSPORT:
                for op in topo.tracer:
                    if ori == op.origine and dst == op.destination:
                        if cost != 0 and op.cost == cost:
                            return op
                        else:
                            return op
            return False

        ''' Retourne l'entrepot dont le nom est "wh_name"'''
	def getWarehouse(self, topo, wh_name):
		for wh in topo.warehouses:
			if wh.name == wh_name:
				return wh
		return False
	
	''' Retourne la ville dont le nom est "city_name"'''
	def getCity(self, topo, city_name):
		for city in topo.cities:
			if city.name == city_name:
				return city
		return False

	''' Retourne la route dont l'entrepot est "wh_name" et la ville de destination "city_name"'''
	def getRoad(self, topo, wh_name, city_name):
		for road in topo.roads:
			if road.warehouse == wh_name and road.city == city_name:
				return road
		return False

	''' Check s'il reste encore des villes dans le besoin'''
	def isCitiesInNeed(self, S):
		for city in S.cities:
			if city.current_needs > 0:
				return True
		return False

        ''' Fonction de calcul de cout d'une topologie'''
        def f(self, S):
            total_cost = 0
            for trace in S.tracer:
                total_cost += trace.cost
            return total_cost
            
	''' Algo du tabou'''
	def taboo(self):
		nbStable = 0
		
		# Config initiale
		S = self.SGlouton.topology
		
		# 'Optimal'
		best = self.f(S)
				
		# Init list taboo
		self.listTaboo = ListTaboo()
		
		while nbStable < 500:
			# On prend le meilleur voisin
			Sbis = self.generateBestNeighbour(S, k)

			# Check si le coût de Sbis est meilleur que celui de S
			if self.f(Sbis) < best:
				# MAJ de la liste tabou
				self.listTaboo.addTaboo(S)
				
				best = self.f(Sbis)
				S = Sbis
				nbStable = 0

			else:
				nbStable += 1
			
		# Retourne meilleur solution
		print '**** BEST SOLUTION ****'
		total_cost = 0
		for trace in S.tracer:
			print trace.display()
			total_cost += trace.cost
		print 'Cout obtenu : ' + str(total_cost)
		return S
 
